import java.util.*;

/**
 * Description:
 * Date: 2025-11-15
 * Time: 15:05
 */
public class BinaryTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
      }
    }

    public TreeNode creatTree() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        /*nodeC.right = nodeG;
        nodeE.right = nodeF;*/

        return nodeA;
    }

    //二叉树的层序遍历  https://leetcode.cn/problems/binary-tree-level-order-traversal/
    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> qu1 = new ArrayDeque<>();
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> list = new ArrayList<>();
        qu1.offer(root);
        while(!qu1.isEmpty()) {
            List<Integer> qu2 = new ArrayList<>();
            int len = qu1.size();
            for (int i = 0; i < len; i++) {
                TreeNode cur = qu1.poll();
                if(cur.left != null) {
                    qu1.offer(cur.left);
                }
                if(cur.right != null) {
                    qu1.offer(cur.right);
                }
                qu2.add(cur.val);
            }
            list.add(qu2);

        }
        return list;
    }

    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            TreeNode cur = deque.poll();
            if (cur == null) {
                break;
            }
            deque.offer(cur.left);
            deque.offer(cur.right);
        }
        while (!deque.isEmpty()) {
            TreeNode cur = deque.poll();
            if(cur != null) {
                return false;
            }
        }
        return true;
    }

    //二叉树的最近公共祖先  https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
    /*
    * 列出所有情况，进行判断
    * 当前节点有可能的情况：
    * ①：节点是p ②：节点是q ③：节点为null  (此时返回该节点)
    * ④：其它情况：(1)p、q都在左子树 (2)：p、q都在右子树 (3)p、q在左右子树 (4)左右子树都没有
    *            (1)(2)返回该子树，(3)进行左右子树返回值的判断，(4)返回null，已经进行过判断后，最终就是null返回自身结束当前空间的递归
    * */
    //递归实现
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode leftT = lowestCommonAncestor1(root.left,p,q);
        TreeNode rightT = lowestCommonAncestor1(root.right,p,q);
        if (leftT != null && rightT != null) {
            return root;
        }
        if (leftT != null) {
            return leftT;
        }
        if (rightT != null) {
            return rightT;
        }
        return null;
    }

    //模拟链表具有公共节点：若有最近公共祖先，则两节点必定都走过，记录节点各自走过的路线(一层为一步)
    //                 先让长的先走，等处于同一层时，同时返回，第一个相同节点就是最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> stackQ = new ArrayDeque<>();
        Deque<TreeNode> stackP = new ArrayDeque<>();
        isSame(root,q,stackQ);
        isSame(root,p,stackP);
        int len = stackQ.size() - stackP.size();
        if (len > 0) {
            while (len != 0) {
                stackQ.pop();
                len--;
            }
        }else {
            len = -len;
            while (len != 0) {
                stackP.pop();
                len--;
            }
        }
        while (!stackQ.isEmpty() && !stackP.isEmpty()) {
            if (stackQ.peek() == stackP.peek()) {
                return stackQ.peek();
            }
            stackQ.pop();
            stackP.pop();
        }
        return null;
    }

    public TreeNode isSame(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
        if (root == null) {
            return root;
        }
        stack.push(root);
        if(root == node) {
            return root;
        }
        TreeNode leftT = isSame(root.left,node,stack);
        TreeNode rightT = isSame(root.right,node,stack);
        if (leftT != null) {
            return leftT;
        }
        if(rightT != null) {
            return rightT;
        }
        stack.pop();
        return null;
    }

    //从前序与中序遍历序列构造二叉树  https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return assistT(preorder,inorder,0,inorder.length-1);
    }
    //遍历前序数组，保持下标不受递归影响
    public int index = 0;
    public TreeNode assistT(int[] preorder, int[] inorder,int left,int right) {
        //通过选择区间来选择左右子树，并规定了递归结束条件
        if (left > right) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[index]);

        int target = findVal(preorder[index],inorder);
        index++;

        root.left = assistT(preorder,inorder,left,target-1);
        root.right =  assistT(preorder,inorder,target+1,right);
        return root;
    }

    public int findVal(int key, int[] inorder){
        for (int i = 0; i < inorder.length; i++) {
            if (key == inorder[i]) {
                return i;
            }
        }
        return -1;
    }

    //从中序与后序遍历序列构造二叉树  https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        index1 = postorder.length-1;
        return assistZH(inorder,postorder,0,postorder.length-1);
    }
    public int index1 = 0;
    public TreeNode assistZH(int[] inorder,int[] postorder,int left,int right) {
        if(left > right) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[index1]);
        int target = findVal(postorder[index],inorder);
        index1--;
        root.right = assistZH(inorder,postorder,target+1,right);
        root.left = assistZH(inorder,postorder,left,target-1);
        return root;
    }

    //根据二叉树创建字符串  https://leetcode.cn/problems/construct-string-from-binary-tree/
    public String tree2str(TreeNode root) {
        //字符串的构造进行添加使用StringBuilder或StringBuffer
        StringBuilder str = new StringBuilder();
        inorderStr(root,str);
        return str.toString();
    }

    public void inorderStr(TreeNode root, StringBuilder str) {
        if (root == null) {
            return;
        }
        str.append(root.val);
        //只针对左子树的情况(左右子树中的左子树，不涉及右子树的遍历)
        if (root.left != null) {
            str.append("(");
            inorderStr(root.left,str);
            str.append(")");
        }else {
            if (root.right != null) {
                str.append("()");
            }else {
                return;
            }
        }
        //只针对右子树的情况(左右子树中的右子树，不涉及左子树的遍历)
        if (root.right != null) {
            str.append("(");
            inorderStr(root.right,str);
            str.append(")");
        }else {
            return;
        }
    }

    //二叉树前序遍历非递归遍历实现  https://leetcode.cn/problems/binary-tree-preorder-traversal/
    public List<Integer> preorderTraversal(TreeNode root) {
        //利用栈结构来实现
        Deque<TreeNode> qu = new ArrayDeque<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null || !qu.isEmpty()) {
            //循环左子树
            while (cur != null) {
                qu.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            //左子树走完，继续走右子树
            TreeNode top = qu.pop();
            cur = top.right;
        }
        return list;
    }

    //二叉树中序遍历非递归遍历实现  https://leetcode.cn/problems/binary-tree-inorder-traversal/
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> qu = new ArrayDeque<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null || !qu.isEmpty()){
            while (cur != null) {
                qu.push(cur);
                cur = cur.left;
            }
            TreeNode top = qu.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }

    //二叉树后序遍历非递归遍历实现  https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> qu = new ArrayDeque<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        TreeNode curN = null;

        while (cur != null || !qu.isEmpty()) {
            while (cur != null) {
                qu.push(cur);
                cur = cur.left;
            }
            TreeNode top = qu.peek();
            //两种情况都满足的情况下可以打印出当前根节点
            //①：在左子树为空的前提下，右子树也为空
            //②：在左子树为空的前提下，右子树已经被出过了(没有这个条件陷入死循环)
            if (top.right != null && curN != top.right) {
                cur = top.right;
            } else {
                curN = qu.pop();
                list.add(curN.val);
            }

        }
        return list;
    }

}
